% Chapter Template

%\chapter{Domain filtering consistencies} % Main chapter title
\chapter{Filtrage plus fort que DC}
\label{Chapter3} % Change X to a consecutive number; for referencing this chapter elsewhere, use \ref{ChapterX}

\lhead{Chapitre 3. \emph{Filtrage plus fort que DC}} % Change X to a consecutive number; this is for the header on each page - perhaps a shortened title

La conception de consistance locale est au cœur de la programmation par contraintes. La consistance locale est utilisée pendant la recherche pour réduire l'espace de recherche en découvrant les inconsistances. Dans ce chapitre, nous abordons les consistances plus fortes que DC pour les contraintes binaires et non binaires. D'abord, nous présentons les consistances pour les contraintes binaires, la comparaison entre elles. Puis, nous passons aux consistances pour les contraintes non-binaires. En fait, ces consistances sont inspirées par les consistances pour les contraintes binaires. La comparaison entre ces consistances est aussi examinée.

%La consistance qui n'enlève que la valeur de domaine et ne change pas la structure du CSP est appelée la consistance de filtrage de domaine. L'intérêt pour appliquer ces consistance est que la complexité du problème ne change pas.
 

%----------------------------------------------------------------------------------------
%	SECTION 1
%----------------------------------------------------------------------------------------
\section{Filtrage plus fort que DC pour contraintes binaires}

Dans cette section, les consistances les plus importantes dans la littérature  pour les contraintes binaires sont abordées. D'abord les consistances se basant sur les triplets de variables (RPC, PIC, Max-RPC) sont présentées. Puis nous présentons les consistances se basant sur les variables voisines d'une variable (elles sont liées par une contrainte) (NIC) ou se basant sur l’assignation hypothétique d’une valeur à une variable (SAC).

%-----------------------------------
%	SUBSECTION 1
%-----------------------------------
\subsection{Consistances à base de triangle}

%The first local consistency following this line of research is Restricted Path Consistency (RPC), proposed by Berlandier [13]. The motivation for RPC is to remove more inconsistent values than arc consistency whereas avoiding the cost of path consistency. Path consistency removes all pairs of values that cannot be extended to a third variable.The idea of RPC is to try to extend only those pairs of values that if removed, would lead to arc inconsistency of a value. So, in addition to arc consistency, RPC guarantees path consistency of the pairs of values $((x_i , v_i ), (x_j , v_j ))$ that are the only support for $(x_i, v_i )$ on $c_{ij}$.  If such a pair is path inconsistent, its deletion would lead to the arc inconsistency of $(x_i , v_i)$. Thus $(x_i , v_i)$ can be removed. These few additional path consistency checks allow the detection of more inconsistent values than arc consistency without having to delete any pair of values, and so leaving the structure of the network unchanged.

\begin{definition}[Restricted Path Consistency (RPC)]
Un CSP binaire $(X,D(X),C)$ est \textit{restricted path consistent (RPC)} ssi il est \textit{DC} et $\forall x_i \in X, \forall a \in D(x_i), \forall c_{ij}(x_i, x_j) \in C$ telle que $(x_i,a)$ a un seul support $(x_j,b)$ sur $c_{ij}(x_i, x_j)$, alors $\forall x_k \in X$ lié à la fois $x_i, x_j$ par contrainte, il existe $c \in D(x_k)$ telle que $c_{ik}(a,c) \wedge c_{jk}(b,c)$.

\end{definition}

%\textbf{Complexité de l'algorithme le plus efficace}
%RPC is strictly stronger than AC. An example of a network on which RPC prunes more values than AC is shown in ~\ref{fig:RPC_DC}. Berlandier proposed an algorithm in O(end3 ). The optimal complexity of achieving RPC on a binary normalized network is in O(en + ed2 + td2), where t is the number of triples of variables (xi , xj , xk ) with cij , cjk and cik all in C. An algorithm with this optimal time complexity was presented by Debruyne and Bessiere \cite{debruyne2001domain}.

RPC est strictement plus fort que DC \cite{debruyne2001domain}. Un CSP que RPC enlève plus de valeur que DC est montré dans la figure ~\ref{fig:RPC_DC}. L'algorithme optimal pour RPC est l'algorithme RPC2, il est proposé dans \cite{debruyne1997restricted} avec une complexité temporelle de $O(en + ed^2 + cd^2)$, une complexité d'espace en $O(ed+cd)$ où $c$ est le nombre de triples de variables $(x_i, x_j, x_k)$ avec $c_{ij}, c_{jk}, c_{ki} \in C$.

%\begin{itemize}
%\item RPC2: time complexity is $O(en + ed^2 + cd^2)$ , space complexity is $O(ed+cd)$ \cite{debruyne2001domain}
%
%where c is number of the triples of variables $(x_i, x_j, x_k)$ with $c_{ij}, c_{jk}, c_{ki} \in C$
%\end{itemize}
%
%\textbf{RPC} is strictly stronger than \textbf{DC} \cite{debruyne2001domain}

	\begin{figure}[ht]
	\centering
	\includegraphics[height=4.6cm]{./images/binary/RPC_DC.png}
	\caption{Un exemple de CSP sur lequel RPC enlève plus de valeurs que DC: $(x_i , 1)$ n'est pas RPC tandis que
	ce CSP est DC}
	\label{fig:RPC_DC}
	\end{figure}

%---------------------------------------------------------------------------------------------
\begin{definition}[Path Inverse Consistency (PIC)] Un CSP binaire $(X,D(X),C)$ est \textit{path inverse consistent (PIC)} ssi $\forall x_i \in X, \forall a \in D(x_i), \forall x_j,x_k \in X$, il existe $b \in D(x_j), c \in D(x_k)$ telle que $c_{ij}(a,b) \wedge c_{ik}(a,c) \wedge c_{jk}(b,c)$.
\end{definition}

%PIC is strictly stronger than RPC. An example of a network on which PIC prunes more values than RPC is shown in ~\ref{fig:PIC_RPC}. Freuder and Elfe proposed an algorithm in O(en2 d4). In [41], Debruyne proposed some sufficient conditions for the path-inverse consistency of a network. They permit to avoid some constraint checks. Debruyne presented an optimal algorithm for PIC that runs in O(en + ed2 + td3) with space complexity is $O(ed+cd)$ \cite{debruyne2001domain}.

Un algorithme optimal pour PIC est proposé dans \cite{debruyne2000property} avec complexité temporelle de $O(en + ed^2 + cd^3)$, une complexité d'espace en $O(ed+cd)$ où $c$ est le nombre de triples de variables $(x_i, x_j, x_k)$ avec $c_{ij}, c_{jk}, c_{ki} \in C$. PIC est strictement plus fort que RPC \cite{debruyne2001domain}. Un CSP que PIC enlève plus de valeur que RPC est montré dans la figure ~\ref{fig:PIC_RPC}.

	\begin{figure}[ht]
	\centering
	\includegraphics[height=4.6cm]{./images/binary/PIC_RPC.png}
	\caption{Un exemple de CSP sur lequel PIC enlève plus de valeurs que RPC: $(x_i , 1)$ n'est pas PIC tandis que ce CSP est RPC}
	\label{fig:PIC_RPC}
	\end{figure}
	
%---------------------------------------------------------------------------------------------
\begin{definition}[Max-restricted Path Consistency]
Un CSP binaire $(X,D(X),C)$ est \textit{max-restricted-path consistent (Max-RPC)} ssi $\forall x_i \in X, \forall a \in D(x_i), \forall c_{ij}(x_i,x_j) \in C$, il existe $b \in D(x_j)$ telle que $c_{ij}(a,b)$ et $\forall x_k \in X$, il existe $c \in D(x_k)$ telle que $c_{ij}(a,b) \wedge c_{ik}(a,c) \wedge c_{jk}(b,c)$. %$((x_i,a), (x_j,b), (x_k,c))$ \textit{locally consistent}
\end{definition}

%An optimal algorithm for Max-RPC1 was proposed in \cite{debruyne1997restricted}: with time complexity is $O(en + ed^2 + cd^3)$, and space complexity is $O(ed+cd)$ \cite{debruyne2001domain} where c is number of the triples of variables $(x_i, x_j, x_k)$ with $c_{ij}, c_{jk}, c_{ki} \in C$.

Pour Max-RPC, l'algorithme Max-RPC1 est proposé dans \cite{debruyne1997restricted}. Il est optimal avec une complexité temporelle de $O(en + ed^2 + cd^3)$, une complexité d'espace en $O(ed+cd)$ où $c$ est le nombre de triples de variables $(x_i, x_j, x_k)$ avec $c_{ij}, c_{jk}, c_{ki} \in C$. Max-RPC est prouvé plus fort que PIC \cite{debruyne2001domain}. La figure ~\ref{fig:MaxRPC_PIC} montre un CSP sur lequel MaxRPC enlève plus de valeur que PIC.

%\textbf{Max-RPC} is strictly stronger than \textbf{PIC} \cite{domain:2001}
%
%\begin{itemize}
%\item \textbf{Max-RPC $\longrightarrow$ PIC $\longrightarrow$ RPC}
%\end{itemize}
	\begin{figure}[ht]
	\centering
	\includegraphics[height=4.8cm]{./images/binary/MaxRPC_PIC.png}
	\caption{Un exemple de CSP sur lequel Max-RPC enlève plus de valeurs que PIC : $(x_i , 1)$ n'est pas Max-RPC
	tandis que ce CSP est PIC}
	\label{fig:MaxRPC_PIC}
	\end{figure}

%-----------------------------------
%	SUBSECTION 2
%-----------------------------------
\subsection{Consistance selon le voisinage}
\begin{definition}[Neighborhood Inverse Consistency (NIC)] Un CSP binaire $(X,D(X),C)$ est \textit{neighborhood inverse consistent (NIC)} ssi $\forall x_i \in X, \forall a \in D(x_i)$, 
 $(x_i, a)$ peut être étendu à une instanciation consistante de toutes les variables dans le voisinage de $x_i$ (les variables liées avec $x_i$ dans une contrainte).
\end{definition}

%An algorithm for NIC was proposed in [57]. It runs in $O(g^2(n + ed)d^{g+1})$, where $g$ is the maximum degree of a variable in the associated hypergraph. It is not proved optimal. Anyway, it seems difficult to go below the exponential factor $nd * d^g$ because every value of every variable must be proved consistent with its neighborhood (possibly of size $g$). 
%NIC is strictly stronger than maxRPC. An example is show in ~\ref{fig:NIC_MaxRPC}.

Un algorithme pour NIC est proposé dans \cite{freuder1996neighborhood} dont la complexité temporelle est $O(g^2(n + ed)d^{g+1})$, la complexité d'espace est $O(n)$ où $g$ est le maximum nombre de variable voisine d'une variable (elle sont liées par une contrainte) dans le CSP \cite{debruyne2001domain}. NIC est strictement plus fort que MaxRPC. Un exemple est montré dans la figure ~\ref{fig:NIC_MaxRPC}.

%\textbf{Complexité de l'algorithme le plus efficace}
%\begin{itemize}
%\item NIC1: time complexity is $O(g^2(n + ed)d^{g+1})$ , space complexity is $O(n)$, where $g$ is the maximum degree of a variable in the associated hypergraph \cite{domain:2001} \cite{handbook:2005}
%\end{itemize}
%
%\textbf{NIC} is strictly stronger than \textbf{Max-RPC} \cite{domain:2001}

%\textbf{Example}
	\begin{figure}[ht]
	\centering
	\includegraphics[height=5cm]{./images/binary/NIC_Max-RPC_img.png}
	\caption{Un exemple de CSP sur lequel NIC enlève plus de valeurs que Max-RPC : $(x_i , 1)$ n'est pas NIC tandis que ce CSP est Max-RPC}
	\label{fig:NIC_MaxRPC}
	\end{figure}

%-----------------------------------
%	SUBSECTION 3
%-----------------------------------
\subsection{Consistance de singleton}
\begin{definition}
Un CSP binaire $(X,D(X),C)$ est \textit{singleton arc consistent (SAC)} ssi $\forall x_i \in X, \forall a \in D(x_i)$, le sous problème $(X, D(X)_{x_i = a}, C)$ peut être rendu DC.
\end{definition}


%Bessiere and Debruyne showed that the complexity of SAC on binary normalized networks is in $O(end3)$, and they proposed SAC-Opt, an algorithm with this optimal time complexity [16, 17]. To achieve optimal time, SAC-Opt stores a lot of information in large data structures that require  space. 

Pour SAC, l'algorithme le plus rapide est SAC-Opt \cite{bessiere2005optimal} dont la complexité temporelle est $O(end^3)$. Cependant, sa complexité d'espace est grande $O(end^2)$. SAC est strictement plus fort que MaxRPC. Un exemple d'un CSP sur lequel SAC enlève plus de valeur que MaxRPC est montré dans ~\ref{fig:SAC_MaxRPC}. SAC et NIC sont incomparable \cite{debruyne2001domain}.

%\textbf{Complexité de l'algorithme le plus efficace}
%\begin{itemize}
%\item SAC1: time complexity is $O(en^2d^4)$ , space complexity is $O(ed)$ \cite{domain:2001}
%\end{itemize}

%\textbf{SAC} is strictly stronger than \textbf{Max-RPC}
%
%but \textbf{SAC} and \textbf{NIC} are incomparable \cite{debruyne2001domain}

	\begin{figure}[ht]
	\centering
	\includegraphics[height=4.8cm]{./images/binary/SAC_MaxRPC.png}
	\caption{Un exemple de CSP sur lequel SAC enlève plus de valeur que Max-RPC : $(x_i , 2)$ n'est pas SAC tandis que ce CSP est Max-RPC}
	\label{fig:SAC_MaxRPC}
	\end{figure}

%-----------------------------------
%	SUBSECTION 4
%-----------------------------------
\subsection{Résumé}
Nous avons présenté les consistances plus fortes que DC pour la contrainte binaire. La figure ci-dessous ~\ref{fig:sommary_binary} montre la comparaison entre ces consistances. La flèche montre que telle consistance est plus forte que l'autre. Le tiret montre qu'elles sont incomparable. Dans l'article \cite{debruyne2001domain}, l'auteur a montré une démonstration complète pour cette comparaison.

	\begin{figure}[ht]
	\centering
	\includegraphics[height=2.8cm]{./images/binary/comparison_consistency2.png}
	\caption{Résumé de la comparaison entre les consistances}
	 \label{fig:sommary_binary}
	\end{figure}

\section{Filtrage plus fort que DC pour contraintes non binaires}

%Many strong local consistency techniques have prohibitive space and time complexities. One way around this problem is to use domain filtering consistencies since they require limited space as they only prune domains. We will define three domain filtering consistencies for non-binary constraints inspired by the definitions of RPC, PIC and maxRPC for binary constraints. RPC, PIC and maxRPC specify that every value in the domain of a variable must allow a consistent extension on every second variable, and they also specify conditions on how this consistent pair of values can be extended to a third variable.
%
%Our generalizations to the non-binary case specify that every value in the domain of a variable must allow a GAC-support on every constraint, and they also specify conditions on how this GAC-support can be extended to another constraint. For example, when enforcing PIC we remove values that cannot be consistently extended to any set of two other variables. When enforcing rPIC (the generalization of PIC) we will remove values that cannot be extended to satisfy any set of two constraints.

Dans cette section, nous allons présenter les consistances fortes pour les contraintes non binaires qui sont inspirées par les consistances précédentes (RPC, PIC, Max-RPC,\dots).  RPC, PIC et Max-RPC spécifient que chaque valeur dans un domaine d'une variable doit être extensible à une deuxième variable, et cette valeur peux s'étendre aux troisième variable selon des conditions. Pour les contraintes non binaires, chaque valeur dans un domaine d'une variable doit avoir un GAC-support pour chaque contrainte, et ce GAC-support peut s'étendre à une autre contrainte selon les conditions précisées dans les consistances.

%----------------------------------------------------------------------------------------
\subsection{Restricted Pairwise Consistency (RPWC)}
\begin{definition}[Restricted Pairwise Consistency]
Un CSP non-binaire $(X, D(X), C)$ est \textit{restricted pairwise consistent (RPWC)} ssi $\forall x_i \in X,$ toutes les valeurs dans $D(x_i)$ est GAC et, $\forall a \in D(x_i), \forall c_j \in C,$ $x_i \in vars(c_j),$ telle que il existe un seul tuple valide $\tau \in rel(c_j)$ avec $\tau[x_i] = a$ \textbf{alors} $\forall c_k \in C,$ $vars(c_j) \cap vars(c_k) \neq \emptyset,$ $\exists \tau' \in rel(c_k),$ telle que $\tau[vars(c_j) \cap vars(c_k)]= \tau'[vars(c_j) \cap vars(c_k)]$ et $\tau'$ et valide.
\end{definition}
	
La définition de RPWC est inspirée par la définition de RPC. D'abord GAC est appliqué, ensuite, RPWC enlève des valeurs de la variable $x_i$ qui ont un seul tuple $\tau$ (GAC-support) dans la contrainte $c_j$ et que ce support ne peut pas s'étendre à un tuple valide $\tau'$ dans chacune des contraintes intersectées avec $c_j$. Par définition, RPWC est strictement plus fort que GAC. Un exemple ci-dessous montre cette propriété. Pour obtenir RPWC, l'algorithme RPWC1 est proposé dans \cite{bessiere2008domain} avec une complexité temporelle de $O(ne^2k^2d^k)$ et une complexité d'espace en $O(ekd)$.

\begin{example} $D(x_1)=D(x_2)=D(x_3)=\{1,2,3\}$, $c_1=allDifferent(x_1,x_2,x_3)$, $c_2=x_1=x_2$. Ce CSP est GAC mais il n'est pas RPWC  parce que $(x_1,1), (x_1,2), (x_1,3), (x_2,1)$, $(x_2,2), (x_2,3)$ ne sont pas RPWC.
\end{example}


%----------------------------------------------------------------------------------------
\subsection{relational Path Inverse Consistency (rPIC)}
\begin{definition}[relational Path Inverse Consistency]
Un CSP non-binaire $(X, D(X), C)$ est \textit{relational path inverse consistent (rPIC)} ssi $\forall x_i \in X, \forall c_j \in C,$ $x_i \in vars(c_j)$, et $\forall c_k \in C,$  $vars(c_j) \cap vars(c_k) \neq \emptyset,$ \textbf{alors} $\exists \tau \in rel(c_j)$ telle que $\tau[x_i]=a$, $\tau$ est valide, et $\exists \tau' \in rel(c_k)$ telle que $\tau[vars(c_j)\cap vars(c_k)] = \tau'[vars(c_j)\cap vars(c_k)]$ et $\tau'$ est valide.
\end{definition}

rPIC est inspiré par PIC. Quand on applique rPIC pour un CSP, on considère un paire de contrainte $c_j, c_k$ et voit si une valeur $a\in D(x_i), x_i \in vars(c_j)$ a un GAC-support $\tau$ dans $c_j$ telle que ce support peut être extensible au tuple $\tau'$ dans $c_k$. Dans le cas où on ne trouve aucun $\tau$, alors la valeur $a$ est enlevée. rPIC est montré strictement plus fort que RPWC dans \cite{bessiere2008domain}. L'idée est que dans le cas où une valeur a plus qu'un GAC-support ($\geq 2$ supports), rPIC est plus fort que RPWC et dans le cas où une valeur n'a qu'un GAC-support, rPIC est égale RPWC. Dans l'exemple ci-dessous, le CSP est RPWC mais il n'est pas rPIC. L'algorithme pour rPIC est proposé dans \cite{bessiere2008domain} dont la complexité temporelle est $O(e^2k^2d^p)$ et la complexité d'espace est $O(e^2kd)$ où $p$ est le nombre maximum de variables impliquées dans deux contraintes.

\begin{example}
Etant donné un CSP : $D(x_1)=D(x_2)=D(x_3)=\{0,1,2\}$, $D(x_4)=\{0,1\}$. $c_1=$ allDifferent$(x_1,$ $x_2,x_3),$ $c_2=$ allDifferent$(x_2,x_3,x_4)$. 
Ce CSP est RWPC car les valeurs dans le domaine de variables ont au moins deux GAC-supports. Cependant, ce CSP n'est pas rPIC car les GAC-supports de $(x_1,2)$ dans $c_1$ : (2, 1, 0), (2, 0, 1) ne peuvent pas s'étendre à $c_2$.
\end{example}



%--------------------------------------------------------------------
\subsection{Max Restrited Pairwise Consistency (Max-RPWC)}
\begin{definition}[Max Restrited Pairwise Consistency]
Un CSP non-binaire $(X, D(X), C)$ est \textit{max restricted pairwise consistent (Max-RPWC)} ssi $\forall x_i \in X,$ $\forall a \in D(x_i), \forall c_j \in C,$ où $x_i \in vars(c_j),$ alors $\exists \tau \in rel(c_j)$ telle que $\tau[x_i]=a$, $\tau$ est valide, \textbf{et} $\forall c_k \in C,$ $vars(c_j) \cap vars(c_k) \neq \emptyset,$ alors $\exists \tau' \in rel(c_k),$  $\tau[vars(c_j) \cap vars(c_k)]= \tau'[vars(c_j) \cap vars(c_k)]$ et $\tau'$ est valide. Dans ce cas, $\tau'$ est PW-support de $\tau$.
\end{definition}

La définition de RPWC est inspirée par la définition de RPC. Dans Max-RPWC, on parcourt chaque valeur $a \in D(x_i), x_i \in vars(c_j)$ pour examiner si elle a un GAC-support qui est extensible aux toutes les contraintes intersectées avec $c_j$. Si on ne le trouve pas, alors cette valeur est enlevée. Max-RPWC est prouvé strictement plus fort que rPIC \cite{bessiere2008domain}. L'exemple ci-dessous montre un CSP qui est rPIC mais n'est pas Max-RPWC Pour appliquer Max-RPWC, des algorithmes sont proposés tels que Max-RPWC1, Max-RPWC2, Max-RPWC3 \cite{bessiere2008domain}. Max-RPWC2 a une meilleure complexité temporelle $O(e^2k^2d^k)$ mais la complexité d'espace est grande ($O(e^2kd^f)$). La complexité temporelle de Max-RPWC1 et Max-RPWC3 est $O(e^2k^2d^p)$. Mais en pratique, Max-RPWC3 est souvent plus efficace que Max-RPWC1. 
	
%\textbf{Algorithms}
%	\begin{itemize}
%	\item \textbf{Max-RPWC-1} complexity of time: $O(e^2k^2d^p)$, of space: $O(ekd)$
%	\item \textbf{Max-RPWC-2} complexity of time: $O(e^2k^2d^k)$, of space: $O(e^2kd^f)$\\
%	  $f$ is the maximum number of intersecting variables on two constraints
%	\item \textbf{Max-RPWC-3} complexity of time: $O(e^2k^2d^p)$, of space: $O(e^2kd)$ 
%	\end{itemize}
%
%\textbf{Max-RPWC} is strictly stronger than \textbf{rPIC}

\begin{example}
	\begin{figure}[ht]
	\centering
	\includegraphics[height=4cm]{./images/non-binary/MaxRPWC_rPIC2.png}
	\caption{MaxRPWC vs. rPIC}
	\label{ex:maxRPWC_rPIC}
	\end{figure}
Etant donné un CSP : $D(x_1)=D(x_2)=D(x_3)=\{0,1\}$, $D(x_4)= D(x_5)=\{0\}$. Les contraintes $c_1,c_2,c_3$ sont présentées dans la figure ~\ref{ex:maxRPWC_rPIC}. Ce CSP est rPIC mais il n'est pas MaxRPWC. Par exemple, la valeur 0 de $x_1$ est rPIC car pour deux contraintes $c_1, c_2$, le GAC-support $(0, 0, 0)$ de $(x_1, 0)$ dans $c_1$ peut s'étendre à $(0, 0, 0)$ dans $c_2$, pour deux contraintes $c_1, c_3$, le GAC-support $(0, 1, 1)$ de $(x_1, 0)$ dans $c_1$ peut s'étendre à $(1, 1, 0)$ dans $c_3$. Mais cette valeur n'est pas Max-RPWC car aucun de ses GAC-supports ne peut s'étendre à la fois $c_2, c_3$.
\end{example}

%Nous avons abordé les consistances de base (RPWC, rPIC, MaxRPWC, \dots), il existe encore des autres consistances \cite{stergiou2006inverse} \cite{stergiou2007strong} \cite{stergiou2008strong}. Dans cette partie, nous ne présentons que deux consistances qui sont inspirées par MaxRPWC.

\subsection{Max Restricted 3-wise Consistency (Max-R3WC)}
\begin{definition}[Max Restricted 3-wise Consistency] Un CSP non binaire $(X, D(X), C)$ est \textit{max restricted 3-wise consistent (Max-R3WC)} ssi $\forall x_i \in X, \forall a \in D(x_i), \forall c_j \in C,$ où $x_i \in vars(c_j), \exists \tau \in rel(c_j)$ telle que $\tau[x_i]=a, \tau$ est valide, \textbf{et} $\forall c_k, c_l \in C$, il existe des tuples valides $\tau' \in rel(c_k), \tau'' \in rel(c_l)$ telle que 
$\tau[vars(c_j)\cap vars(c_k)] = \tau'[vars(c_j)\cap vars(c_k)],$ 
$\tau[vars(c_j)\cap vars(c_l)]=\tau''[vars(c_j)\cap vars(c_l)],$
$\tau'[vars(c_k)\cap vars(c_l)]=\tau''[vars(c_k)\cap vars(c_l)]$.
\end{definition}

Pour chaque valeur $a \in D(x_i), x_i \in vars(c_j)$, on examine si cette valeur a un GAC-support qui peut s'étendre aux deux autres contraintes intersectées avec $c_j$ (Max-RPWC en considère une). Évidement, Max-R3WC est plus fort que Max-RPWC. Pour Max-R3WC, algorithme Max-R3WC1 est proposé dont la complexité temporelle est  $O(e^3k^3d^{p+p'})$, la complexité d'espace est $O(ekd)$ où $p+p'$ est le nombre total de variables impliquées dans 3 contraintes \cite{stergiou2008strong}.
	
%\textbf{Algorithms}
%	\begin{itemize}
%	\item \textbf{R3WC-1} time complexity: $O(e^3k^3d^{p+p'})$ space complexity: extensional constraint $O(ekd)$ \cite{stergiou2008strong}\\
%	$p+p'$: total number of variables involved in 3 constraints
%	\end{itemize}
%
%\textbf{Max-R3WC} is strictly stronger than \textbf{Max-RPWC}

%	\textbf{Max-R3WC} is incomparable to \textbf{rNIC} \cite{stergiou2008strong}
	
%--------------------------------------------------------------------
\subsection{Max Restricted k-wise Consistency (Max-RkWC)}
\begin{definition}[Max Restricted k-wise Consistency] Un CSP non binaire $(X, D(X), C)$ est \textit{max restricted k-wise consistent (Max-RkWC)} ssi $\forall x_i \in X, \forall a \in D(x_i), \forall c_j \in C,$ où $x_i \in vars(c_j), \exists \tau \in rel(c_j)$ telle que $\tau[x_i]=a, \tau$ est valide, \textbf{et} pour un ensemble quelconque de $k-1$ contraintes additionnelles $c_1, \dots, c_{k-1}, \tau$ peut s'étendre à une valide instanciation sur les variables $\bigcup_{m=1}^{k-1}vars(c_m)$ qui satisfait chaque contrainte $c_m$, $m=1,\dots,k-1$.
\end{definition}

Max-RkWC est une généralisation de Max-R3WC. Si Max-RkWC est appliqué sur la variable $x_i$, il enlève la valeur $a \in D(x_i)$ telle que pour les contraintes $c_j$ que $x_i$ participe, aucun GAC-support de $(x_i,a)$ ne peut s'étendre aux tous les ensembles de $k-1$ autres contraintes. 
	
%----------------------------------------------------------------------------------------
\subsection{PWC+GAC}
\begin{definition}[Pairwise Consistency]
Un CSP $(X, D(X), C)$ est \textit{Pairwise Consistent (PWC)} ssi $\forall \tau \in rel(c_i)$, $\tau$ est valide, alors $\tau$ peut s'étendre à chacune de contraintes intersectées avec $c_i$.
\end{definition}

\begin{definition}[PWC+GAC] 
Un CSP $(X, D(X), C)$ est \textit{PWC+GAC} ssi il est \textit{PWC} et \textit{GAC}.
\end{definition}

Pour la consistance PWC+GAC, PWC enlève les tuples à partir de la relation de contrainte. GAC est appliqué pour le filtrage de domaine : la valeur qui n'a pas de support dans une contrainte est enlevée. Dans \cite{bessiere2008domain}, on montre que PWC+GAC est plus fort que Max-RPWC. Ci-dessous un CSP qui est RPWC mais n'est pas PWC+GAC.

\begin{example} 
\begin{figure}[ht]
\centering
\includegraphics[height=3.3cm]{./images/non-binary/PWC_GAC_MaxRPWC2.png}
\caption{PWC+GAC vs. Max-RPWC}
\end{figure}
Etant donné un CSP : $D(x_1)=D(x_2)=D(x_3)=D(x_4)=D(x_5)=\{0,1\}, D(x_6)=\{0\}$. Les trois contraintes $c_1, c_2, c_3$ sont présentées dans la figure ci-dessus. La valeur 0 de $x_1$ a un GAC-support $(0,0,0)$ dans $c_1$. Ce tuple peut s'étendre au tuple $(0, 0, 0, 0)$ dans $c_2$. $(x_1, 0)$ est donc MaxRPWC (aussi pour les autres valeurs). Cependant, le tuple $(0, 0, 0, 0)$ dans $c_2$ ne peut pas s'étendre à $c_3$, ce tuple est enlevé par PWC+GAC. Par conséquence, on doit enlever $(0,0,0)$ dans $c_1$, alors $(x_1, 0)$ est supprimée car elle n'a plus de GAC-support.
\end{example}

%----------------------------------------------------------------------------------------
\subsection{kWC+GAC}
\begin{definition}[k-Wise Consistency (kWC)]
Un CSP $(X, D(X), C)$ est \textit{k-Wise Consistency (kWC)} ssi $\forall c_j \in C, \forall \tau in rel(c_j) : \tau$ est valide, et pour un ensemble quelconque de $k-1$ contraintes additionnelles $c_1, \dots, c_{k-1}$, $\tau$ peut s'étendre à une valide instanciation sur les variables $\bigcup_{i=1}^{k-1}vars(c_i)$ qui satisfait chaque contrainte $c_i, i = 1,\dots, k-1.$
\end{definition}



\begin{definition}[kWC+GAC]
Un CSP $(X, D(X), C)$ est \textit{kWC+GAC} ssi il est kWC et GAC.
\end{definition}

kWC+GAC est une généralisation de PWC+GAC, kWC enlève de tuples qui ne peuvent pas s'étendre à un ensemble quelconque de $k-1$ autres contraintes, GAC enlève des valeurs du domaine de variables. kWC+GAC est plus fort que PWC+GAC.

%----------------------------------------------------------------------------------------
\subsection{relational Neighborhood Inverse Consistent (rNIC)}
\begin{definition}[relational Neighborhood Inverse Consistent] Un CSP non-binaire $(X, D(X), C)$ est \textit{relational neighborhood inverse consistent (rNIC)} ssi $\forall x_i \in X, \forall a \in D(x_i), \forall c_j \in C,$ où $x_i \in vars(c_j), \exists \tau \in rel(c_j)$ telle que $\tau[x_i]=a, \tau$ est valide, \textbf{et} $\tau$ peut s'étendre à une solution du sous problème composé l'ensemble de variables $X_j= \{vars(c_j)\cup vars(c_{j_1})\cup\dots\cup vars(c_{j_m})\},$ où $c_{j_1},\dots,c_{j_m}$ sont les contraintes qui intersectent avec $c_j$.
%\textbf{rNIC} is incomparable to \textbf{Max-R3WC} \cite{strong domain:2008}
\end{definition}

rNIC considère chaque valeur $a \in D(x_i), x_i \in vars(c_j)$ pour voir si cette valeur a un GAC-support dans $c_j$ et ce GAC-support peut s'étendre aux autres contraintes intersectées avec $c_j$. Si non, cette valeur est enlevée. rNIC est strictement plus fort que MaxRPWC parce que rNIC considère toutes les contraintes intersectées avec $c_j$ en même temps au milieu de les prendre séparément. La démonstration est dans \cite{stergiou2008strong}.

%----------------------------------------------------------------------------------------
\subsection{Singleton Generalized Arc Consistency (SGAC)}
\begin{definition}[Singleton Generalized Arc Consistency]
Un CSP $(X, D(X), C)$ est \textit{singleton generalized arc consistent (SGAC)} ssi il n'a pas de domaine vide et pour une assignation quelconque d'une variable, l'application de GAC pour le sous problème $(X, D(X)_{x=a}, C)$ peut rendre \textit{GAC}.
\end{definition}

L'idée de SGAC est que l'on fait l'assignation hypothétique une valeur à une variable et on applique la consistance de GAC pour ce sous problème. Si le résultat est un problème qui est GAC, alors cette valeur est SGAC. Si non cette valeur est supprimée. SGAC est strictement plus fort que RPWC. Par contre, SGAC est incomparable avec rPIC, Max-RPWC, PWC+GAC \cite{bessiere2008domain}. Les exemples ci-dessous montrent cette propriété.

\begin{example} rPIC, Max-RPWC, PWC+GAC ne sont pas plus forts que SGAC

Etant donné un CSP : $D(x_1)=D(x_2)=D(x_3)=\{0,1\}$, $c_1= x_1\neq x_2, c_2= x_2\neq x_3, c_3= x_3\neq x_4, c_4= x_4 = x_1$. Ce CSP est rPIC, Max-RPWC, PWC+GAC but n'est pas SGAC car le sous problème $(X,D(X)_{x_1=0},C)$ ne peut pas être rendu GAC.
\end{example}

\begin{example}
{SGAC} n'est pas plus fort que {rPIC, Max-RPWC, PWC+GAC}

Etant donné un CSP : $D(x_1)=D(x_2)=D(x_3)=\{0,1\}$, $c_1(x_1,x_2, x_3) = \{000,011,100,111\},$ $c_2(x_1,x_2,x_3)=\{001,010,100,111\}$. Ce CSP est SGAC mais n'est pas rPIC, Max-RPWC, PWC+GAC. car aucun GAC-supports de $(x_1,0)$ dans $c_1$ ne peut satisfaire $c_2$.

\label{ex:SGAC vs rPIC, Max-RPWC, PWC+GAC}
\end{example}

$\Longrightarrow$ {SGAC} est incomparable avec {rPIC, Max-RPWC, PWC+GAC}.

\begin{example} SGAC est plus fort que RPWC

Etant donné un CSP : $D(x_1)=D(x_2)=D(x_3)=\{0,1\}$, $c_1= x_1\neq x_2, c_2= x_2\neq x_3, c_3= x_3\neq x_1$. Ce CSP est RPWC mais n'est pas SGAC parce que quand on assigne $x_1 = 0$, le sous problème $(X,D(X)_{x_1=0},C)$ ne peut pas être rendu GAC.
\end{example}



%----------------------------------------------------------------------------------------
\subsection{Résumé}

	\begin{figure}[ht]
	\centering
	\includegraphics[height=2.2cm]{./images/non-binary/comparison_non_binary2.png}
	\caption{Résumé de la comparaison entre les consistances basées sur le domaine pour les contraintes non binaires}
	\label{fig:summary non binaire}
	\end{figure}
	
Nous avons présenté des consistances plus fortes que GAC. La puissance d'élagage de ces consistances est aussi abordé. La figure ci-dessus montre la relation entre elles. La flèche montre qu'une consistance est plus forte que l'autre. La croix montre qu'elles sont incomparable, par exemple : SGAC et MaxRPWC.

	
